package com.sicheng.lc.周赛.分类.贪心;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/19 12:39
 */
public class 小于等于K的最长二进制子序列 {
    //    https://leetcode.cn/problems/longest-binary-subsequence-less-than-or-equal-to-k/
    //大致思路  找到一个后缀最大的合法串，往前补前导0
    // 从低位到高位 当前如果是0直接纳入，如果是1考虑是否纳入
    // 1. 纳入前 已经生成的串 <= k,且纳入后也<=k
    // 2. 纳入前 已经生成的串 >=k
    public int longestSubsequence(String s, int k) {
        long sum = 0;
        int remove = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int j = s.length() - i - 1;
            if (s.charAt(i) == '1') {
                if (sum >= k) {
                    remove++;
                } else {
                    sum += (1L << j);
                    if (sum > k) {
                        remove++;
                    }
                }
            }
        }

        return s.length() - remove;
    }

    public static void main(String[] args) {
        小于等于K的最长二进制子序列 solution = new 小于等于K的最长二进制子序列();
        System.out.println(solution.longestSubsequence("000101010011011001011101111000111111100001011000000100010000111100000011111001000111100111101001111001011101001011011101001011011001111111010011100011110111010000010000010111001001111101100001111"
                , 300429827));
    }

}
